package com.ztr.leetcode.day08;

import java.util.HashSet;

public class LongestSubstring {
    /**
     * 计算字符串中最长无重复字符子串的长度。
     * 在左指针向右移动的时候，我们从哈希集合中移除一个字符，
     * 在右指针向右移动的时候，我们往哈希集合中添加一个字符。
     * @param s 输入的字符串
     * @return 最长无重复字符子串的长度
     */
    public static int lengthOfLongestSubstring(String s) {
        // 使用HashSet来存储当前子串中出现的字符
        HashSet<Character> occ = new HashSet<>();
        int n = s.length(); // 字符串的长度
        int rk = -1, ans = 0; // rk代表滑动窗口的右边界，ans存储最长子串的长度

        for (int i = 0; i < n; ++i){
            // 如果不是第一个字符，则移除窗口中最左边的字符
            if (i != 0){
                occ.remove(s.charAt(i -1 ));
            }
            // 扩展窗口右边界，直到遇到重复字符或窗口右边界达到字符串末尾
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))){
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 更新最长子串的长度
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }

    public static void main(String[] args) {
        String s = "abcabcbb";
        int length = lengthOfLongestSubstring(s);
        System.out.println(length);
    }
}
